package 位运算;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;
/**
 * 这种 类型的 题 还有 好些   关于 数字 出现次数的 题 
 * 那些 使用  异或   ^  就能解决的 那些 使用  异或 运算 解决 不了的 
 * 
 * 本以为 是  直接用    亦或  运算 技巧 解决的  题 但是 结果并不是 这样的 
 * 
 * 思路 ： 原地 哈希 
 * @author I adore you
 *
 */
public class leetcode442数组中重复的数字 {
	
	public static void main(String []args) {
		System.out.println(~4);
		int nums [] = {4,3,2,7,8,2,3,1};
		System.out.println(solutionOne(nums));
	}
	/**
	 *  暴力 写法 
	 *虽然 能 ac 但是 不符合 要求  a
	 *时间复杂度 是 O（N）
	 *但是 空间 复杂度 不是 几个有限 变量 
	 *空间复杂度 是 O（N）
	 */
	static List<Integer> solution(int nums[]){
		List<Integer> ans = new ArrayList<>();
		HashMap<Integer,Integer> map = new HashMap<>();
		for(int i : nums) {
			if(map.containsKey(i))
				ans.add(i);
			else map.put(i,1);
		}
		return ans;
	}
	/**
	 * 什么 原地 哈希 的 技巧	
	 * 这种思想的 原理 其实 就是 哈希的 原理     相同的  东西 会  mapping 到 相同的 东西 （位置上面） 一种 映射 关系
	 https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/solution/by-fuxuemingzhu-dko5/
	 题解链接
	 
 	取反 ~  和 取相反数  可不一样
	 */
	static List<Integer> solutionOne(int nums[]){
		List<Integer> ans = new ArrayList<>();
		for(int i : nums) {
			int temp = Math.abs(i);
			if(nums[temp -1] < 0) {
				ans.add(temp);
			}
			else
				nums[temp -1] = -nums[temp - 1];	
		}
		
		return ans;
		
	}
}
